1. Field of the Invention
The present invention relates generally to improved techniques for pixel data propagation using a linearly connected array of processors, and more specifically to such techniques via which pixel data propagation within a two-dimensional image is implemented at a considerably high speed.
2. Description of the Related Art
In order to specify or distinguish a region from others within a two-dimensional digital image, it is known in the art to use a so-called "parallel propagation processing technique" using a linear processor array. According to this technique, starting from one or more distinctive pixels in the two-dimensional digital image, unique pixel data is written into in parallel to the surrounding pixels. This technique is applicable to the case where a plurality of regions within a two-dimensional image are to be distinguished by labeling different unique numbers to respective regions. Further, the above mentioned technique is also used to determine a shape of a region in a two-dimensional image by tracing the contour thereof. A linear processor array per se is well known in the art, which is disclosed in U.S. Pat. Nos. 5,319,586 and 5,630,154 merely by way of example.
Before turning to the present invention, it is deemed preferable to briefly describe a conventional technique with reference to FIGS. 1A-1C and 2.
FIG. 1A is a diagram schematically showing a two-dimensional pixel image 10 which consists of X by Y pixels. For the sake of simplifying the disclosure, the image 10 is such as to include a region 12 to be specified for later operations which are irrelevant to the present invention. In order to distinguish the region 12 from the remaining portion of the image 10, it is necessary to write unique data into each pixel of the region 12. In brief, the present invention is concerned with the writing of such unique data into an area to be distinguished.
Referring to FIG. 1B, there is shown part of a conventional parallel image processing apparatus 13 which comprises a plurality of local memories 14(1)-14(X), a plurality of buffers 16(1)-16(X), and a plurality of processing elements (PEs) 18(1)-18(X). More specifically, the PEs 18(1)-18(X) are respectively assigned to the one-line pixels stored in the local memories 14(1)-14(X). The image 10 of FIG. 1A is written into the local memories 14(1)-14(X) each of which stores one-column (or one-line) pixel data. A controller 20 controls the overall operation of the PEs 18(1)-18(X).
Assuming that if a given buffer stores a pixel from which the data propagation process is to be initiated, the PE assigned to the buffer in question has already written or registered the address of the propagation start pixel in the buffer.
FIG. 1C is a diagram showing part of the arrangement of FIG. 1B. In FIG. 1C, a center pixel (or reference pixel) in the buffer 14(N) (1&lt;N&lt;X) is a pixel from which data propagation may be implemented to the pixel positions 1-8 which surrounds the center pixel. To be more precise, the pixel positions 1-8 are the possible positions to which a unique data can be propagated. That is, prior to implementing the data propagation, it is necessary to check if the data propagation should be implemented to each pixel position. It is understood that if the pixel position 1 is outside the region to be specified, the data propagation to the position 1 is not permitted. The operations of propagating the data of the center pixel (or reference pixel position) to one of the surrounding pixels are identical with one another, and hence, only the operation from the center pixel to the pixel position 1 will be described with reference to FIG. 2.
In FIG. 2, at step 30, a check is made to determine if data propagation to the pixel position 1 is necessary. If the answer is negative, the operation is terminated. Otherwise, the program goes to step 32 at which the PE 18(N) propagates a unique data to the right neighboring (adjacent) PE 18(N+1). At step 34, PE 18(N) transfers the address of the position 1 to PE(N+1). Following this, at step 36, PE(N+1) writes the unique data propagated from PE(N) to the position 1 whose address has been informed from PE(N). At step 38, PE(N+1) registers the address information of pixel position 1 at the buffer.
The above mentioned conventional technique, however, suffers from the problem that the number of processing steps becomes very large. That is, as shown in FIG. 2, four steps 32, 34, 36 and 38 are necessary at each iteration. Further, if the unique data at the center pixel should be propagated to all the eight surrounding positions 1-8, PE(N) must implement three times of data propagation to each of the right and left adjacent processing elements PE(N-1) and PE(N+1). In addition, PE(N) must carry out the data propagation two times within itself in connection with the position 2 and 7.